﻿// 4926. 中位数.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stdio.h>

using namespace std;
/*
https://www.acwing.com/problem/content/4929/

给定 N个整数 X1,X2,…,XN。

让我们计算每一对数字之间的差值：|Xi−Xj|（1≤i<j≤N）。

通过上述操作，我们一共可以得到 N(N−1)2个差值。

请你找到这些差值的中位数。

在本问题中，设差值的总个数为 m
，如果 m 为偶数，则中位数定义为从小到大排序后的第 m/2 个数，例如，如果 m=6
，则中位数定义为从小到大排序后的第 3个数。

输入格式
输入包含多组测试数据。

每组数据第一行包含整数 N。

第二行包含 N个整数 X1,X2,…,XN。

输出格式
每组数据输出一行结果，一个整数，表示所有差值的中位数。

数据范围
3≤N≤10^5,
0≤Xi≤10^9。
注意，本平台满足 N的最大取值为 10^5
，但是 POJ 官网中 N的实际最大取值不超过 40000。

输入样例：
4
1 3 2 4
3
1 10 2
输出样例：
1
8
*/

const int N = 100010;
int arr[N];
long long n;
long long  limit;


//int  Getbelow(int c, int  x) {
//	//二分获取小于等于x的 个数
//	int  l = c; int  r = n;
//	while (l < r) {
//		int  mid = (l + r + 1) >> 1;
//		if ((arr[mid] - arr[c]) <= x) {
//			l = mid;
//		}
//		else {
//			r = mid - 1;
//		}
//	}
//	return l - c;
//}
//
//bool check(long long  x) {
//	long long  res = 0;
//	for (int i = 1; i <= n; i++) {
//		res += Getbelow(i, x);
//	}
//
//	if (res < limit) {
//		return false;
//	}
//
//	return true;
//}

bool check(long long x) {
	//滑动窗口 计算有多少arr[j]-arr[i]  复杂度O(n)
	long long res = 0; int j = 1;
	for (int i = 1; i <= n; i++) {
		while (j <= n && arr[j] - arr[i] <= x) j++;
		res += j - i-1;
	}

	return res >= limit;
}

void solve() {
	int  l = 0;
	int  r = arr[n] - arr[1] + 10;
	arr[0] = -1;
	limit = n * (n - 1) / 2 / 2;
	if ((n * (n - 1) / 2 % 2) != 0) limit++;

	while (l < r) {
		long long  mid = (l + r) >> 1;
		if (check(mid)) {
			r = mid;
		}
		else {
			l = mid + 1;
		}
	}
	printf("%d\n", l);
}


int main()
{
	while (~scanf("%d", &n)) {
		for (int i = 1; i <= n; i++) { scanf("%d", &arr[i]); }
		sort(arr + 1, arr + 1 + n);
		solve();
	}

	return 0;
}

